#include <iostream>
#include <vector>

// 标准库中的所有容器都支持迭代器
// 可以写一个统一的模板函数
template <typename T>
void Print(const T &v)
{
    for (auto ite = v.begin(); ite != v.end(); ite++)
    {
        std::cout << *ite << " ";
    }
    std::cout << std::endl;
}

int main()
{
#if 0
    // vector是模板实现的，所以要带<>，里面放上类型
    std::vector<int> v; // 定义一个容器
    v.push_back(1); // 尾插
    v.pop_back();   // 尾删 O(1)
    std::cout << v.capacity() << std::endl; // 数组的容量
    std::cout << v.size() << std::endl; // 数组的元素个数
#endif

#if 0
    std::vector<int> v = {1, 2, 3, 4}; // 另一种初始化方式
    for (int i = 0; i < v.size(); i++)
    {
        std::cout << v[i] << " "; // 动态数组重载了[]，所以可以根据下标去访问列表中的每一个元素
    }
    std::cout << std::endl;
#endif

#if 0
    std::vector<int> v = {1, 2, 3, 4};

    // 迭代器是定义在容器内部的一个结构体
    // begin()：容器的头部迭代器，指向容器的第一个元素
    std::vector<int>::iterator ite = v.begin();
    // 迭代器重载了*，用取星号解引用操作，所以不难看出它的底层是指针
    // 所以迭代器的本质是指针，它只是对指针的一次封装
    std::cout << *ite << std::endl;
#endif

#if 0
    std::vector<int> v = {1, 2, 3, 4};
    // 迭代器写起来太长了，可以用auto自动推导类型
    auto ite = v.begin();
    std::cout << *ite << std::endl;
#endif

#if 0
    std::vector<int> v = {1, 2, 3, 4};
    // begin()：容器的头部迭代器，指向容器的第一个元素的位置
    auto ite_start = v.begin();
    // end()：容器的尾部迭代器，指向容器的最后一个元素的下一个位置
    // 它是内存的下一个位置，这个位置一般来说是不允许取的
    auto ite_end = v.end();
    // end这个位置其实是没有内存的，但是在容器里编译器会对其进行优化
    // 由于这里是普通数据类型（int），会被优化成0，但如果是自定义数据类型（像student这种类的对象），取出来大概率就会崩掉，因为那个内存没有办法优化
    // std::cout << *ite_end << std::endl;
    // 那这么一来就可以得到一种全新的对容器的访问形式，推荐以这种方式遍历容器
    // 这是一种更标准、更通用的格式
    // 因为不会每一种容器都支持[]重载，但是会支持迭代器，标准库中的所有容器都支持迭代器
    // 于是可以写一个统一的模板函数，见上
    for (auto ite = v.begin(); ite != v.end(); ite++)
    {
        std::cout << *ite << " ";
    }
    std::cout << std::endl;
#endif

#if 0
    std::vector<int> v = {1, 2, 3, 4};
    // 可以直接+是因为迭代器重载了+
    // 随机迭代器
    v.insert(v.begin() + 2, 99); // 插入
    Print(v);
    v.erase(v.begin() + 2); // 删除
    Print(v);
#endif

#if 0
    std::vector<int> v = {1, 99, 2, 99, 3, 99};

    // 所有容器的按值删除都可以这么写，不会出问题
    for (auto ite = v.begin(); ite != v.end();)
    {
        if (*ite == 99)
        {
            // 迭代器失效问题：
            // 当一个容器删掉某一个迭代器所在位置的数据的时候，那么当前指向这个位置的迭代器也会失效
            // v.erase(ite); // 元素被删除，迭代器会失效
            // erase函数有一个返回值：指向下一个元素的迭代器，所以当把这个位置删掉，要把下一个位置取出来，必须要这样写，否则ite++会出问题
            ite = v.erase(ite);
        }
        // ite没有修改的情况下才可以++
        else
        {
            ite++;
        }
    }
#endif

#if 1
    std::vector<int> v = {1, 99, 2, 99, 3, 99};

    // 清空容器中的所有元素
    v.clear();
    
    // 取出某个位置的元素
    v.at(10); // 会抛出越界异常
    v[10]; // 不会抛异常

    // 理论上容器能取到的最大容量
    std::cout << v.max_size() << std::endl;

    // 扩容
    v.resize(20);
    std::cout << v.capacity() << std::endl;

    // 缩减内存到size
    v.shrink_to_fit();
#endif

    return 0;
}